The present invention generally relates to soft input/soft output algorithms, many varieties of which are used in communication signal processing, and particularly relates to the use of sliding windows in soft input/soft output processing.
As the term implies, soft input/soft output (SISO) algorithms receive soft values as inputs, and produce corresponding soft values as outputs. Maximum a posteriori (MAP) processing is one example of a SISO algorithm, and finds widespread use in many signal-processing applications, such as in decoding turbo codes, which are built from the concatenation of two or more relatively simple convolutional codes.
In more detail, Turbo coding encodes a desired information sequence, also referred to as the “systematic” sequence, using two or more convolutional encoders. The resulting coded output includes the outputs of each convolutional encoder, along with the systematic sequence. Because the original information sequence is part of the coded output, turbo codes represent a type of “systematic” code.
In one approach to decoding turbo codes, a MAP decoder receives a sequence of bit soft values, e.g., probability distributions or Log-Likelihood-Ratios (LLRs), representing a turbo encoded sequence of bits. In turn, the MAP decoder improves the ability to make subsequent “hard” decisions on the systematic bit soft values by forming better and better estimates of the corresponding a posteriori probabilities of the systematic bits based on knowledge of the coding structure.
The so-called “BCJR” algorithm represents a popular implementation of the MAP algorithm for turbo decoding, and gains processing advantages by exploiting the trellis structure of convolutional codes. Assuming an input sequence of LLRs corresponding to coded bits and systematic bits in a turbo coded sequence, the BCJR algorithm refines the LLRs of the systematic bits based on its determination of forward and backward state metrics and branch metrics for each systematic bit. In turn, those determinations rely on knowledge of the trellis structure and on the input soft values of the systematic and parity bits.
In one approach to improving BCJR and other trellis-based decoding, encoded sequences include known starting and/or ending values. Adding known values to the beginning and end of an encoded sequence allows the corresponding decoder to begin and end trellis traversal with known starting and ending states, which improves the reliability of the output probability estimates. However, fully traversing the trellis from the known starting values to the known ending values in one sweep, sometimes referred to as “full frame” processing or traversal, imposes significant memory requirements, given potentially long trellis lengths and the need to accumulate state metrics throughout.
One approach to reducing memory requirements involves subdividing the trellis into a number of windows, and then processing each window separately. This approach, which may be referred to as “sliding window” traversal or processing, accumulates state metrics only over the length of each window, which generally is substantially less than the length of the overall trellis. However, with forward and backward recursion in each window, recursion starts “cold” at an unknown state, at least within the intermediate windows lying between the first and last windows subdividing the trellis. These unknown starting states result in poor reliability of the output soft values, at least until the algorithm “warms up” by accumulating state metrics over a number of stages within the window. These lower reliabilities generally translate into lower decoder performance, resulting in reduced communication link performance. The possibility for the recursions to warm up from unknown starting (or ending) states also forms the practical basis of decoding a tail-biting trellis, where the path corresponding to the true information sequence starts and ends in the same state.
The sliding windows can be overlapped to mitigate this reliability problem, with more overlap generally translating into greater mitigation. However, because the trellis stages within the overlap regions are processed in each one of two overlapping windows, more overlap disadvantageously translates into lower decoder throughput. Besides, even large overlap does not satisfactorily alleviate the reliability problem at the higher data rates afforded by Wideband CDMA (W-CDMA) and other developing wireless communication standards.
More broadly, memory concerns come into play with SISO-based processing of potentially lengthy soft value sequences, whether or not the SISO algorithm uses trellis-based processing. Thus, it is common practice to use sliding window traversal in processing the overall sequence—i.e., the overall sequence is subdivided using a series of overlapped windows. As such, the above-mentioned reliability concerns come into play across a broad range of SISO algorithms wherein windowed traversal is used.